package graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import utils.binaryTreeUtil;

public class Trie {
    boolean end;
    Trie[] children;

    public Trie() {
        end=false;
        children = new Trie[26];
    }

    public void insert(String word) {
        // 判断是否存在，是则不用插入了
        if (!search(word)) {
            Trie trie = this;
            for (char c : word.toCharArray()) {
                if (trie.children[c-'a']==null) {
                    trie.children[c-'a']=new Trie();
                }
                trie=trie.children[c-'a'];
            }
            trie.end=true;
        }
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node!=null&&node.end;
    }
    public Trie searchPrefix(String word){
        Trie trie = this;
        for (char c : word.toCharArray()) {
            if (trie.children[c-'a']!=null) {
                trie=trie.children[c-'a'];
            }else{
                return null;
            }
        }
        return trie;
    }
    public boolean startsWith(String prefix) {
         return searchPrefix(prefix)!=null;
    }
}
